package com.timous.动态规划;
/**
 * https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
 */
public class _剑指Offer47_礼物的最大价值 {


    /**
     * 二位数组
     * @param grid
     * @return
     */
    public int maxValue(int[][] grid) {
        if (grid == null) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];
        // 初始化0行
        for (int i = 1; i < cols; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        //初始化0列
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                dp[row][col] = Math.max(dp[row-1][col] , dp[row][col-1]) + grid[row][col];
            }
        }
        return dp[rows-1][cols-1];
    }

    /**
     * 一维数组
     * @param grid
     * @return
     */
    public int maxValue1(int[][] grid) {
        if (grid == null) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        int[] dp = new int[cols];
        int count = 0;
        //循环的次数
        dp[0] = grid[0][0];
        for (int i = 1; i < cols; i++) {
            dp[i] = dp[i-1] + grid[0][i];
        }
        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                if (col - 1 == 0){
                    dp[0] = dp[0] + grid[row][0];
                }
                // 比较左边和上面值的大小 ， 如果是上面值是比较大的就选上面的 ， 反之选择最下面的
                dp[col] = Math.max(dp[col-1] , dp[col]) + grid[row][col];
//                dp[col] = dp[col-1] + grid[row][col];
            }
        }
        return dp[cols - 1];
    }
}
